package pers.qianyu.month_202012.date_20201212;

import java.util.*;

/**
 * 503. 下一个更大元素 II
 * https://leetcode-cn.com/problems/next-greater-element-ii/
 *
 * @author mizzle rain
 * @date 2020-12-12 17:04
 */
public class NextGreaterElements {
    public int[] nextGreaterElements(int[] nums) {
        int len = nums.length;
        int[] res = new int[len];
        Stack<Integer> s = new Stack<>();
        for (int i = 2 * len - 1; i >= 0; i--) {
            while (!s.isEmpty() && s.peek() <= nums[i % len]) {
                s.pop();
            }
            res[i % len] = s.isEmpty() ? -1 : s.peek();
            s.push(nums[i % len]);
        }
        return res;
    }
}
